#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<unordered_map>
#include<map>
#include<set>
#include<cstdio>
#include<chrono>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e7+100;
typedef int LL;
inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
unordered_map<LL,LL,custom_hash>map1;
LL a[maxn];
LL v[maxn],primes[maxn];
void getprimes(LL n)
{
	LL m=0;
	for(LL i=2;i<=n;i++){
		if(v[i]==0) {v[i]=i;primes[++m]=i;}
		for(LL j=1;j<=m;j++){
			if(primes[j]>v[i]||primes[j]>n/i)	break;
			v[i*primes[j]]=primes[j];
		}
	}
}
LL solve(LL x){
    LL mul=1;
    while(x>1){
        LL cnt=0;
        LL temp=v[x];
        while(x%temp==0){
            x/=temp;
            cnt++;
        }
        if(cnt&1) mul*=temp;
    }
    if(x>1) mul*=x;
    return mul;
}
int main(void)
{
  getprimes(10000000);
  LL t;t=read();
  while(t--){
    LL n,k;n=read();k=read();
    map1.clear();

    for(LL i=1;i<=n;i++) a[i]=read();

    for(LL i=1;i<=n;i++) a[i]=solve(a[i]);

    LL ans=1;
    map1[a[1]]++;
    for(LL i=2;i<=n;i++){
        if(map1.count(a[i])){
            ans++;
            map1.clear();
        }
        map1[a[i]]++;
    }
    printf("%d\n",ans);
  }
return 0;
}
